package org.zjt.algorithm;

/**
 * 连续的元素的最大和区间
 */
public class MaxSum {
    public static void main(String[] args) {
        int[] array = new int[]{1,2,-2,3,3,-2,3,-89,2,10,1};
        int start,end,max;
        start = 0;
        end = 0;
        max = array[0];
        for (int i = 0;i < array.length;i ++){
            int sum = array[i];
            for (int j = i + 1;j < array.length;j ++){

                //得到连续集合最大数。
                if (sum + array[j] >= 0){
                    sum += array[j];
                }else{
                    break;
                }

                // 保存最大区间
                if (sum > max){
                    max = sum;
                    end = j;
                    start = i;
                }
            }
        }
        System.out.printf("start:%d end:%d sum:%d",start,end,max);
    }
}
